赛纲介绍
本次题目的总体题目难度如下，各位选手可以借此评估一下自身的技术水平
题目编号 题目名称 题目难度 T1 未出现的人 入门 T2 gcd 普及- T3 a + b 普及- T4 礼物 普及/提高- T5 聊天室 普及+/提高 T6 BFS 普及+/提高
未出现的人
题目大意
题目的要求是现在有 nnn 个姓名互不相同的同学， 其中 mmm 个人出席了本场会议，求未出场本比赛的学生的名单。
题解思路
我们可以采用标记法来解决这一问题。首先，建立一个数据容器，将所有原计划参加讲座的学生姓名依次存储其中，构建完整的学生列表。接着，在记录实际出席学生的过程中，对已出现的学生姓名在列表中进行标记，以此区分出席与未出席的学生。最后，对存储学生姓名的列表进行遍历，将所有未被标记的学生姓名输出，这些学生即为缺席讲座的人员，如此便能清晰呈现缺席学生名单 。
参考代码
GCD
题目大意
你可以选择一个任意长度的子序列 ab1,ab2,…a_{b_1},a_{b_2},\dotsab1 ,ab2 ,… 。 然后求得子序列的最大公因数 ggg 。 将子序列每一个数 abia_{b_i}abi 变为 abi×(g+1)g\frac{a_{b_i} \times (g+ 1 )}{g}gabi ×(g+1) 。之后对于整个数组求最大公因数是多少。
题解思路
思考一下gcd(x ,x+1) 是多少，答案是 111,因此，我们如果选择一个子序列的最大公因数为 ggg ，那么我们所有因子包含 ggg 的数都要被选举，否则整个数组最终的 gcdgcdgcd 为 111。
因此我们可以枚举自己期望求的最大公因数是多少，之后我们对所有包含期望因子的求 gcdgcdgcd,对不包含的数也求另外一组 gcdgcdgcd ，之后进行相应的操作
参考代码
A + B
题目大意
使用三个集合的数生成三个数 aaa , bbb , ccc ，满足 a+b=ca + b = ca+b=c。
题解思路
命题证明：若存在整数 A,B,C<109A,B,C < 10^9A,B,C<109 满足 A+B=CA + B = CA+B=C，则至少存在一组解使得 A,B,C<100A,B,C < 100A,B,C<100
证明思路
1. 基于进位特性的范围收缩：通过分析加法运算中每一位的进位情况，将可能的解空间从 10910^9109 量级逐步缩小至两位数范围。
2. 个位情况分类讨论：以个位加法是否进位作为突破口，分情况证明存在小范围解。
3. 两位数等式的普适性：利用“每一位都进位”的假设，将多位数问题转化为两位数问题。
详细证明过程
假设：存在三个整数 a,b,c∈Za,b,c \in \mathbb{Z}a,b,c∈Z，满足 a+b=ca + b = ca+b=c 且 0≤a,b,c<1090 \leq a,b,c < 10^90≤a,b,c<109，其中 a,b,ca,b,ca,b,c 由三个特定字符集构建。
1. 个位加法的基础分析
由于 a+b=ca + b = ca+b=c，等式成立的必要条件是个位数字满足 a0+b0≡c0(mod10)a_0 + b_0 \equiv c_0 \pmod{10}a0 +b0 ≡c0 (mod10)（其中 x0x_0x0 表示整数 xxx 的个位数字）。
* 情况一：个位无进位
若 a0+b0=c0a_0 + b_0 = c_0a0 +b0 =c0 且 a0+b0<10a_0 + b_0 < 10a0 +b0 <10，此时取 a′=a0,b′=b0,c′=c0a' = a_0, b' = b_0, c' = c_0a′=a0 ,b′=b0 ,c′=c0 ，显然 a′,b′,c′<10<100a',b',c' < 10 < 100a′,b′,c′<10<100，命题得证。
* 情况二：个位有进位
若 a0+b0=c0+10a_0 + b_0 = c_0 + 10a0 +b0 =c0 +10（即向十位进位），此时需进一步分析十位数字的组合情况。
2. 基于进位条件的十位分析
假设个位进位为 111，若字符集 ScS_cSc 中不包含数字 111，则无法通过更高位的运算消除个位进位带来的影响，导致等式不成立。因此，若有解且个位进位，则 1∈Sc1 \in S_c1∈Sc 是必要条件。
* 此时，为使等式成立，十位数字需满足 a1+b1+1=c1a_1 + b_1 + 1 = c_1a1 +b1 +1=c1 （其中 x1x_1x1 表示整数 xxx 的十位数字），等价于 a1+b1=c1−1a_1 + b_1 = c_1 - 1a1 +b1 =c1 −1。若能找到满足此条件的 a1,b1,c1a_1,b_1,c_1a1 ,b1 ,c1 ，则可构造出两位数解 a′=10a1+a0,b′=10b1+b0,c′=10c1+c0a' = 10a_1 + a_0, b' = 10b_1 + b_0, c' = 10c_1 + c_0a′=10a1 +a0 ,b′=10b1
+b0 ,c′=10c1 +c0 ，且 a′,b′,c′<100a',b',c' < 100a′,b′,c′<100。
3. 多位数问题向两位数的转化
由于假设每一位加法均产生进位，对于任意长度的 a,b,ca,b,ca,b,c，其每一段连续两位的数字组合（首尾拼接）均需满足加法进位规则。因此，验证所有可能解的充分条件是验证所有两位数组合，即只需在 0≤a,b,c<1000 \leq a,b,c < 1000≤a,b,c<100 的范围内寻找解。
结论
通过对个位进位情况的分类讨论，结合多位数进位的普遍规律，证明了若存在满足 a+b=ca + b = ca+b=c 且 a,b,c<109a,b,c < 10^9a,b,c<109 的整数解，则必然存在一组解使得 a,b,c<100a,b,c < 100a,b,c<100。此结论将解空间显著缩小，为后续算法设计提供了理论依据。
参考代码
礼物
题目大意
你现在有 mmm 元钱，现在有 nnn 中不同的物品。每种物品有一个花费 cic_ici 和幸福值 viv_ivi ,你每次可以购买两个不同的物品，你的朋友会收下幸福度较低的一个，问你的朋友最大可以获得多少幸福度
题解思路
我们希望找到所有幸福值大于等于自己的元素中花费最少的应该是多少，这样我们可以先按照幸福值进行排序，之后我们可以用一个类似于前缀最小值的方法找到相应的花费，活着直接枚举也可以。
问题就转换为一个 nnn 个物品， mmm 点花费的完全背包。
参考代码
聊天室
题目大意
一天一共有 nnn 个时刻 ，其中有 mmm 个线段，每一个线段从 lil_ili 开始， 到 rir_iri 结束。现在有 qqq 次询问，每次询问有一个 lil_ili rir_iri did_idi ,问已知区间有没有能和现在的区间相交为 did_idi 。
题解思路
题目分析
这个问题描述了一个场景：Alice 有 m 位网友，每位网友每天在固定的时间段 [li,ri][l_i, r_i][li ,ri ] 内可以聊天。接下来有 q 天，每天 Alice 会在 [ui,vi][u_i, v_i][ui ,vi ] 时间段内寻找网友聊天，如果能找到一位网友可以持续聊天 d_i 时长，就能放松。我们需要判断每一天 Alice 是否能成功放松。
解题思路
1. 问题转化：我们需要判断是否存在一位网友，其在线时间段 [li,ri][l_i, r_i][li ,ri ] 与 Alice 的查询时间段 [ui,vi][u_i, v_i][ui ,vi ] 的交集长度 ≥di\ge d_i≥di 。
2. 关键观察：
* 交集长度 = min(ri,vi)−max(li,ui)+1≥dimin(r_i, v_i) - max(l_i, u_i) + 1 \ge d_imin(ri ,vi )−max(li ,ui )+1≥di
* 可以转化为三种情况：
* a) 网友的右端点足够大：ri≥ui+di−1r_i \ge u_i + d_i - 1ri ≥ui +di −1
* b) 网友的左端点足够小：li≥vi−di+1l_i \ge v_i - d_i + 1li ≥vi −di +1
* c) 网友的在线时长足够长：ri−li+1≥dir_i - l_i + 1 \ge d_iri −li +1≥di
3. 数据结构选择：
* 使用线段树（Segment Tree）来高效查询区间信息
* 分别处理上述三种情况，用三个线段树来维护
参考代码
BFS
题目大意
给出一个求 BFSBFSBFS 序的方法，求 BFSBFSBFS 序的种类数。
题解思路
问题1：组合排列中的经典计数问题
给定 aaa 个完全相同的红球与 bbb 个完全相同的篮球，将它们排成一排，求不同排列情况的总数。这是一个典型的组合问题，可利用组合数公式求解。由于在总共 a+ba + ba+b 个位置中，只需确定 aaa 个红球的位置（篮球位置随之确定），因此排列情况数为组合数 (a+ba)\binom{a + b}{a}(aa+b )。
问题2：树上BFS序的计数问题
对于给定的一棵树，我们的目标是计算从根节点出发，所有可能的广度优先搜索（BFS）序的数目。这里，我们采用树上动态规划的策略来解决。
动态规划过程中，假设当前已处理到节点 iii，并且已经考虑了其子树的一个特定集合 SSS。其中，集合 SSS 包含的节点总数为 x1x_1x1 ，该集合内所有节点构成的子结构可能产生的BFS序的数量为 p1p_1p1 。此时，若要将一个新的子树纳入考虑范围，该子树的节点数为 x2x_2x2 ，其自身可能的BFS序数量为 p2p_2p2 。那么，将新子树加入后形成的新集合 S1S_1S1 ，其可能的BFS序数量可通过如下方式计算：
根据分步乘法计数原理，先将原集合 SSS 的 p1p_1p1 种情况与新子树的 p2p_2p2 种情况进行组合，得到 p1×p2p_1 \times p_2p1 ×p2 种初步组合。进一步考虑到新子树节点与原集合节点在BFS遍历顺序中的相对位置关系，本质上是在 x1+x2x_1 + x_2x1 +x2 个位置中选择 x1x_1x1 个位置放置原集合节点（剩余位置放置新子树节点），所以最终新集合 S1S_1S1 可能的BFS序数量为 p1×p2×(x1+x2x1)p_1 \times p_2 \times \binom{x_1 + x_2}{x_1}p1 ×p2 ×(x1 x1 +x2
)。通过这样逐步扩展子树集合，自底向上地进行动态规划计算，最终可得到从根节点出发的所有可能BFS序的数目。
问题3：换根DP实现任意节点的BFS序计数
在求解出以1号节点为根时的BFS序情况数后，为了计算以其他节点为根时的情况数，我们引入换根动态规划的方法。
具体操作上，首先针对当前根节点，将其某一棵子树的情况从原有计算结果中去除，消除该子树对当前根节点计算的影响。随后，通过精心设计的状态转移规则，将相关状态信息合理地转移到新选定的根节点上，从而实现从不同节点视角重新计算BFS序的情况数。通过遍历每个节点作为根节点，完成整个换根DP过程，即可得到树中任意节点作为根时可能的BFS序数目。
参考代码
